package tree.threadedbinarytree;


//线索化二叉树 中序
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        //测试中序线索二叉树
        HeroNode root = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6, "smith");
        HeroNode node4 = new HeroNode(8, "mary");
        HeroNode node5 = new HeroNode(10, "king");
        HeroNode node6 = new HeroNode(14, "dim");

        //手动创建二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        //测试线索化
        ThreadedBinaryBinaryTree binaryTree = new ThreadedBinaryBinaryTree();
        binaryTree.setRoot(root);
        binaryTree.threadedNodes(root);
        //测试
        HeroNode leftNode = node5.getLeft();
        //前驱
        System.out.println(leftNode);
        //后继
        HeroNode rightNode = node5.getRight();
        System.out.println(rightNode);
        System.out.println("使用线索化中序遍历二叉树");
        binaryTree.threadedList();

    }
}

//线索化二叉树
class ThreadedBinaryBinaryTree {
    private HeroNode root;

    //当前节点的前驱节点指针
    private HeroNode pre = null;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    //遍历中序线索化二叉树的方法
    public void threadedList() {
        HeroNode node = root;
        while (node != null) {
            //找到leftType=1的节点  随着遍历而变化
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }
            //打印当前节点
            System.out.println(node);
            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }
            //替换这个遍历的节点
            node = node.getRight();

        }


    }


    public void threadedNodes() {
        this.threadedNodes(root);
    }

    public void threadedNodes(HeroNode node) {
        //如果node 不能为线索化
        if (node == null) {
            return;
        }
        //先线索化左子树
        threadedNodes(node.getLeft());
        //线索化当前节点

        //前驱
        if (node.getLeft() == null) {
            node.setLeft(pre);
            //修改类型
            node.setLeftType(1);
        }
        //后继
        if (pre != null && pre.getRight() == null) {
            //让前驱节点的指针指向当前节点
            pre.setRight(node);
            pre.setRightType(1);
        }
        //让当前节点是下一个节点的前驱
        pre = node;
        //线索化右子树
        threadedNodes(node.getRight());
    }


    public void perOrder() {//前序遍历
        if (this.root == null) {
            System.out.println("当前二叉树为空不能遍历");
        } else {
            this.root.preOrder();
        }
    }

    public void infixOrder() {//中序遍历
        if (this.root == null) {
            System.out.println("当前二叉树为空不能遍历");
        } else {
            this.root.infixOrder();
        }
    }

    public void postOrder() {//后序遍历
        if (this.root == null) {
            System.out.println("当前二叉树为空不能遍历");
        } else {
            this.root.postOrder();
        }
    }

    public HeroNode preOrderSearch(int No) {
        if (this.root == null) {
            System.out.println("当前二叉树为空不能遍历");
        }
        return this.root.preOrderSearch(No);

    }

    public HeroNode postOrderSearch(int No) {
        if (this.root == null) {
            System.out.println("当前二叉树为空不能遍历");
        }
        return this.root.postOrderSearch(No);

    }

    public HeroNode infixOrderSearch(int No) {
        if (this.root == null) {
            System.out.println("当前二叉树为空不能遍历");
        }
        return this.root.infixOrderSearch(No);

    }

    public void delNode(int no) {
        if (this.root == null) {
            System.out.println("当前二叉树为空不能遍历");
        } else if (root.getNo() == no) {
            root = null;
            return;
        } else {
            root.delNode(no);
        }
    }

}


class HeroNode {
    private int no;
    private String name;

    private HeroNode left;   //默认为null
    private HeroNode right;     //默认为null

    //如果lefttype=0表示指向左子树   如果是1则表示指向前驱节点
    //rightType=0表示指向右子树   如果是1则表示指向后驱节点
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" + "no=" + no + ", name='" + name + '}';
    }

    //前序遍历  父左右
    public void preOrder() {
        System.out.println(this); //先输出父节点
        if (this.left != null) { //向左递归
            this.left.preOrder();
        }
        if (this.right != null) { //向右递归
            this.right.preOrder();
        }
    }

    //中心遍历  左父右
    public void infixOrder() {
        if (this.left != null) { //向左递归
            this.left.infixOrder();
        }
        System.out.println(this); //输出父节点

        if (this.right != null) { //向右递归
            this.right.infixOrder();
        }
    }

    //后续遍历  左右父
    public void postOrder() {
        if (this.left != null) { //向左递归
            this.left.postOrder();
        }
        if (this.right != null) { //向右递归
            this.right.postOrder();
        }
        System.out.println(this); //输出父节点
    }

    //前序查找
    public HeroNode preOrderSearch(int No) {

        HeroNode temp = null; //用于接收查找到的值
        if (this.left != null) {
            temp = this.left.preOrderSearch(No);
        }
        if (this.no == No) {
            return this;
        }
        if (temp != null) {
            return temp;
        }
        if (this.right != null) {
            temp = this.right.preOrderSearch(No);
        }
        return temp;
    }

    //中序查找
    public HeroNode infixOrderSearch(int No) {
        HeroNode temp = null; //用于接收查找到的值
        if (this.left != null) {
            temp = this.left.infixOrderSearch(No);
        }
        if (temp != null) {
            return temp;
        }
        if (this.no == No) {
            return this;
        }
        if (this.right != null) {
            temp = this.right.infixOrderSearch(No);
        }
        return temp;
    }


    //后序查找
    public HeroNode postOrderSearch(int No) {
        HeroNode temp = null; //用于接收查找到的值
        if (this.left != null) {
            temp = this.left.postOrderSearch(No);
        }
        if (temp != null) {
            return temp;
        }

        if (this.right != null) {
            temp = this.right.postOrderSearch(No);
        }
        if (this.no == No) {
            return this;
        }
        return temp;
    }

    //删除
    public void delNode(int no) {
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        //向左递归 删除
        if (this.left != null) {
            this.left.delNode(no);
        }
        //向右递归 删除
        if (this.right != null) {
            this.right.delNode(no);
        }
    }

}